package com.fc.primary.sort;

import java.util.Random;

/**
 * @program: fc-java->Fast
 * @description: fast
 * @author: G_Y
 * @create: 2019-09-01 22:01
 * 挖坑填数
 **/
public class Fast {

    private static int[] arr = new int[50];
    private static int len = arr.length;

    static {
        Random r = new Random();
        for (int i = 0; i < 50; i++) {
            arr[i] = r.nextInt(100);
        }
        say();
    }

    public static void main(String[] args) {
        fast();
    }

    public static void fast() {
        quickSort(arr, 0, arr.length - 1);
        System.out.println("------------------------");
        say();
    }


    private static int partition(int[] arr, int left, int right) {
        int temp = arr[left];
        while (right > left) {
            // 先判断基准数和后面的数依次比较
            while (temp <= arr[right] && left < right) {
                --right;
            }
            // 当基准数大于了 arr[right]，则填坑
            if (left < right) {
                arr[left] = arr[right];
                ++left;
            }
            // 现在是 arr[right] 需要填坑了
            while (temp >= arr[left] && left < right) {
                ++left;
            }
            if (left < right) {
                arr[right] = arr[left];
                --right;
            }
        }
        arr[left] = temp;
        return left;
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (arr == null || left >= right || arr.length <= 1)
            return;
        // 找出
        int mid = partition(arr, left, right);
        quickSort(arr, left, mid);
        quickSort(arr, mid + 1, right);
    }

    public static void say() {
        for (int a : arr) {
            System.out.print(a + " ");
        }
    }
}
